<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var minDepth = function (root) {
        // 方法一：递归（）---时间O（N）（其中 N 是树的节点数，对每个节点访问一次）
        // ---空间：O（H）（树的高度，空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为 O(N)，平均情况下树的高度与节点数的对数正相关，空间复杂度为 O(log⁡N)）
        // let minD = Number.MAX_SAFE_INTEGER;
        // if (!root) {
        //   return 0;
        // }
        // if (!root.left && !root.right) {
        //   return 1;
        // }
        // if (root.left) {
        //   minD = Math.min(minDepth(root.left), minD);
        // }
        // if (root.right) {
        //   minD = Math.min(minDepth(root.right), minD);
        // }
        // return minD+1;

        // 方法二：遍历（）---时间O（N）（）---空间：O（N）（）
        const arr = [root];
        let minD = 0;
        if (!root) {
          return minD;
        }
        while (arr.length) {
          const length = arr.length;
          for (let i = 0; i < length; i++) {
            const node = arr.shift();
            if (!node.left && !node.right) {
              return minD+1;
            }
            if (node.left) {
              arr.push(node.left);
            }
            if (node.right) {
              arr.push(node.right);
            }
          }
          minD++;
        }
      };

      const treeObj = {
        val: 4,
        left: {
          val: 2,
          left: { val: 1, left: null, right: null },
          right: { val: 3, left: null, right: null },
        },
        right: {
          val: 7,
          left: { val: 6, left: null, right: null },
          right: { val: 9, left: null, right: null },
        },
      };
      const treeObj1 = {
        val: 4,
        left: {
          val: 2,
          left: { val: 1, left: null, right: null },
        },
      };
      // console.log(minDepth(treeObj));
      console.log(minDepth(treeObj1));
    </script>
  </body>
</html>
